using System;
using System.Linq;

namespace Algorithm.LeetCode
{
    /// <summary>
    /// 第二十六题
    /// </summary>
    public class No26
    {
        /*
         * 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
         *
         * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
         */

        public static int RemoveDuplicatesV1(int[] nums)
        {
            var temp = nums.Distinct().ToArray();
            for (var i = 0; i < nums.Length; i++)
            {
                nums[i] = temp.Length > i ? temp.Skip(i).First() : 0;
            }

            return temp.Length;
        }

        public static int RemoveDuplicatesV2(int[] nums)
        {
            var lastItem = default(int?);
            var result = 0;
            for (var i = 0; i < nums.Length; i++)
            {
                if ((lastItem.HasValue && nums[i] == lastItem) || (i + 1 < nums.Length && nums[i] > nums[i + 1]))
                {
                    nums[i] = nums[i + 1];
                    nums[i + 1] = 0;
                    continue;
                }

                lastItem = nums[i];
                result++;
            }

            Array.Sort(nums);
            return result;
        }
    }
}